package binaryTree;

import java.util.*;

public class D230718 {
    // 一、二叉树的前序遍历
    // 1. 递归
    private List<Integer> list = new ArrayList<>();
    public int[] preorderTraversal (TreeNode root) {
        preorder(root);
        int[] res = new int[list.size()];
        int i = 0;
        for (int val : list) {
            res[i++] = val;
        }
        return res;
    }

    private void preorder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 根
        list.add(root.val);
        // 左
        preorder(root.left);
        // 右
        preorder(root.right);
    }

    // 2. 栈
    public int[] preorderTraversal2 (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            // 访问节点，再向左走并存储节点
            while (root != null) {
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }

            // 左走到底了，出栈，向右边走
            if (!stack.isEmpty()) {
                root = stack.pop();
                root = root.right;
            }
        }
        int[] res = new int[list.size()];
        int i = 0;
        for (int val : list) {
            res[i++] = val;
        }
        return res;
    }


    // 二、二叉树的中序遍历
    // 1. 递归
    private List<Integer> list2 = new ArrayList<>();
    public int[] inorderTraversal (TreeNode root) {
        inOrder(root);
        int[] res = new int[list2.size()];
        int i = 0;
        for (int val : list2) {
            res[i++] = val;
        }
        return res;
    }

    private void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 左
        inOrder(root.left);
        // 根
        list2.add(root.val);
        // 右
        inOrder(root.right);
    }
    // 2. 栈
    public int[] inorderTraversal2 (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            // 向左走并存储节点
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            // 左走到底了，出栈，访问节点，再向右走
            if (!stack.isEmpty()) {
                root = stack.pop();
                list.add(root.val);
                root = root.right;
            }
        }
        int[] res = new int[list.size()];
        int i = 0;
        for (int val : list) {
            res[i++] = val;
        }
        return res;
    }


    // 三、二叉树的后序遍历
    // 1. 递归
    private List<Integer> list3 = new ArrayList<>();
    public int[] postorderTraversal (TreeNode root) {
        postorder(root);
        int[] res = new int[list3.size()];
        int i = 0;
        for (int val : list3) {
            res[i++] = val;
        }
        return res;
    }
    private void postorder(TreeNode root){
        if (root == null) {
            return;
        }
        // 左
        postorder(root.left);
        // 右
        postorder(root.right);
        // 根
        list3.add(root.val);
    }
    // 2. 栈
    public int[] postorderTraversal2 (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            // 向左走并存储节点
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 左走到头了
            root = stack.peek();
            // 栈顶节点的右边 为空 或 是已走过的节点
            if (root.right == null || root.right == pre) {
                // 出栈，访问节点
                // 记录这个节点，避免再次往右走
                pre = stack.pop();
                list.add(root.val);
                root = null;
            } else {
                // 栈顶节点的右边不为空，且
                root = root.right;
            }

        }
        int[] res = new int[list.size()];
        int i = 0;
        for (int val : list) {
            res[i++] = val;
        }
        return res;
    }


    // 四、求二叉树的层序遍历
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int count = queue.size(); // 记录每层的节点数
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < count; i++) {
                root = queue.poll();
                list.add(root.val);
                if (root.left != null) {
                    queue.add(root.left);
                }
                if (root.right != null) {
                    queue.add(root.right);
                }
            }
            ret.add(list);
        }
        return ret;
    }
}
